//
// Created by 周智超 on 2020/5/26.
//

#ifndef STRUCTURE_SQLIST_H
#define STRUCTURE_SQLIST_H

#include <iostream>
#include "normal.h"

typedef struct {
    int data[maxSize];
    int length;
} Sqlist;

void initList(Sqlist &L)
{
    L.length = 0;
}

int findElem(Sqlist &L, int x)
{
    int i ;
    for(i = 0; i < L.length; i++)
    {
        if(x == L.data[i])
        {
            return i;
        }
    }
    return -1;
}


int insertElem(Sqlist &L, int p, int e)
{
    int  i;
    if (p < 0 || p>L.length||L.length == maxSize)
        return 0;
    for(i = L.length - 1; i >= p; --i)
    {
        L.data[i + 1] = L.data[i];
    }
    L.data[p] = e;
    ++(L.length);
    return 1;
}
int deleteElem(Sqlist &L, int p, int &e)
{
    int i;
    if(p < 0 || p > L.length - 1) {
        return 0;
    }
    e = L.data[p];
    for(i = p; i < L.length - 1; i++)
    {
        L.data[i] = L.data[i+1];
    }
    --(L.length);
    return 1;
}


int getElem(Sqlist &L, int p, int &e)
{
    if(p < 0 || p > L.length -1)
        return 0;
    e = L.data[p];
    return 1;
}

void reserve(Sqlist &L, int left, int right)
{
    int i, j,  tmp;
    for(i = left, j = right; j > i; i++,j--)
    {
        tmp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = tmp;
    }
}

void exercise_41_1_4(Sqlist &L, int i, int j)
{
    int x ;
    int newLength = L.length - (j - i + 1);
    for(x = j + 1; x < L.length; x++, i++)
    {
        L.data[i] = L.data[x];
    }
    L.length = newLength;
}

void partition(Sqlist &L, int &index)
{
    int i = 0;
    int j = L.length -1;
    int temp = L.data[0];
    while (i < j)
    {
        while (i < j && L.data[j] >= temp) j--;
        if(i < j)
        {
            L.data[i] = L.data[j];
            i++;
        }
        while (i < j && L.data[i] <= temp) i++;
        if(i < j)
        {
            L.data[j] = L.data[i];
            j--;
        }
    }

    L.data[i] = temp;
    index = i;

}


void deleteDup(Sqlist &l)
{
    int cur;
    int i = 0;
    int length = 1;
    cur = l.data[i];
    for (i = 1; i < l.length - 1; i++)
    {
        if(cur != l.data[i])
        {
            l.data[length] = l.data[i];
            length++;
            cur = l.data[i];
        }
    }

    l.length = length;
}

void showList(Sqlist &L)
{
    int i ;
    std::cout << "show_list:";
    for(i = 0; i < L.length; i++)
    {
        std::cout<< L.data[i] << " ";
    }
    std::cout << std::endl;
}



typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;


void showLNode(LNode *p)
{
    p = p->next;
    int i ;
    std::cout << "show_lnode:";
    while (p != NULL)
    {
        std::cout<< p->data << " ";
        p = p->next;
    }
    std::cout << std::endl;
}

void createListR(LNode *&C, int a[], int n)
{
    int i;
    LNode *tmp;
    LNode *cur = NULL;
    C = (LNode *)malloc(sizeof(LNode));
    cur = C;
    for(i = 0; i < n; i++)
    {
        tmp = (LNode *)malloc(sizeof(LNode));
        tmp->data = a[i];
        cur->next = tmp;
        cur = tmp;
    }
    cur->next = NULL;
}

void mergeToHighLow(LNode *&A, LNode *&B, LNode *&C)
{
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *s;
    C = A;
    C->next = NULL;
    free(B);
    while(p != NULL && q != NULL) {
        if(p->data < q->data)
        {
            s = p->next;
            p->next = C->next;
            C->next = p;
            p = s;
        }
        else
        {
            s = q->next;
            q->next = C->next;
            C->next = q;
            q = s;

        }
    }
    while (p != NULL) {
        s = p->next;
        p->next = C->next;
        C->next = p;
        p = s;
    }
    while (q != NULL)
    {
        s = q->next;
        q->next = C->next;
        C->next = q;
        q = s;
    }
}
void exercise_41_1_7(LNode *&A, int &e)
{
    LNode *p, *pre;
    pre = NULL;
    int min;
    p = A;
    for(; p->next != NULL; p = p->next)
    {
        if (pre == NULL || min > p->next->data)
        {
            pre = p;
            min = p->next->data;
        }
    }
    p = pre->next;
    e = p->data;
    pre->next = pre->next->next;
    free(p);
}
void exercise_41_1_8(LNode *&A)
{
    LNode *tail, *p;
    tail = A->next;
    while(tail != NULL && tail->next != NULL)
    {
        tail = tail->next;
    }
    while(A->next != tail)
    {
        p = A->next;
        A->next = A->next->next;
        p->next = tail->next;
        tail->next = p;
    }
}

void exercise_41_1_9(LNode *&A, LNode *&B, LNode *C)
{
    LNode *p, *q, *tmp;
    int i = 1;
    A = (LNode *)malloc(sizeof(LNode));
    B = (LNode *)malloc(sizeof(LNode));
    B->next = A->next = NULL;
    p = A;
    q = B;
    C = C->next;
    while (C != NULL)
    {
        tmp = C->next;
        C->next = NULL;
        if(i % 2 == 1)
        {
            p->next =  C;
            p = C;
        }
        else
        {
            q->next = C;
            q = C;
        }
        C = tmp;
        i++;
    }
}

int exercise_41_2_1(Sqlist &l)
{
   int  i =  (l.data[0] <<4) + 1; //   把数组第0位的数字放在int第4个字节以后当作最小值，并且把遍历第1个元素放在第0个字节到第三个字节
   for(; (i & 15) < l.length; i++)
    {
        if ((i >> 4) > l.data[i&15])
        {
            i = (i & 15) + (l.data[i&15] <<4) ;
        }
    }
    i >>= 4;
   return i;
}



#endif //STRUCTURE_SQLIST_H
